package date_202403

//1671. 得到山形数组的最少删除次数
//
//我们定义 arr 是 山形数组 当且仅当它满足：
//
//arr.length >= 3
//存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
//arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
//arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。
//
//示例 1：
//
//输入：nums = [1,3,1]
//输出：0
//解释：数组本身就是山形数组，所以我们不需要删除任何元素。
//示例 2：
//
//输入：nums = [2,1,1,5,6,2,3,1]
//输出：3
//解释：一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。
//
//
//提示：
//
//3 <= nums.length <= 1000
//1 <= nums[i] <= 109
//题目保证 nums 删除一些元素后一定能得到山形数组。

func minimumMountainRemovals(nums []int) int {
	if len(nums) < 3 {
		return 0
	}

	leftInc := leftMaxIncLength(nums)
	rightDesc := rightMaxIncLength(nums)

	maxLen := 0
	for i := 1; i < len(nums)-1; i++ {
		leftIncNums := leftInc[i]
		rightDecNums := rightDesc[i]
		if leftIncNums > 1 && rightDecNums > 1 {
			maxLen = IntMax5(maxLen, leftIncNums+rightDecNums-1)
		}
		if maxLen == len(nums) {
			break
		}
	}
	return len(nums) - maxLen
}

func leftMaxIncLength(nums []int) []int {
	dp := make([]int, len(nums))
	dp[0] = 1
	for i := 1; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = IntMax5(dp[i], dp[j]+1)
			}
		}
	}
	return dp
}

func rightMaxIncLength(nums []int) []int {
	dp := make([]int, len(nums))
	dp[0] = 1
	for i := 1; i < len(dp); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			iNum := nums[len(nums)-i-1]
			jNum := nums[len(nums)-j-1]
			if jNum < iNum {
				dp[i] = IntMax5(dp[i], dp[j]+1)
			}
		}
	}
	reverseDp := make([]int, len(nums))
	for i, _ := range dp {
		reverseDp[len(nums)-i-1] = dp[i]
	}
	return reverseDp
}

func IntMax5(a, b int) int {
	if a < b {
		return b
	}
	return a
}
